package com.samxcode.leetcode;

/**
 * Given a string S, find the longest palindromic substring in S. You may assume that the maximum
 * length of S is 1000, and there exists one unique longest palindromic substring.
 * 
 * To insert in a special character "#" between letters, both palindromes of odd and even lengths
 * are handled graciously
 * the array p[] record the length of palindromic string at the center of each character
 * 参考：http://www.felix021.com/blog/read.php?2040
 * 
 * @author Sam
 *
 */
public class LongestPalindromicSubstring {

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abcb"));
    }


    public static String longestPalindrome(String s) {
        int lCenterIndex = 0;
        int lLength = 1;
        char[] c = s.toCharArray();
        char[] pc = new char[c.length * 2 + 1];
        pc[0] = '#';
        for (int i = 0; i < c.length; i++) {
            pc[2 * i + 1] = c[i];
            pc[2 * i + 2] = '#';
        }
        int[] p = new int[pc.length];
        int ic = 0;
        int ir = 0;
        for (int i = 1; i < pc.length - 1; i++) {
            int i_mirror = 2 * ic - i; // the mirrored index of i around c
//            if (ir - i > P[j]) 
//                P[i] = P[j];
//            else /* P[j] >= ir - i */
//                P[i] = ir - i; // P[i] >= ir - i，取最小值，之后再匹配更新。
            p[i] = ir > i ? Math.min(p[i_mirror], ir - i) : 1;
            while ((i + p[i]) < pc.length && (i - p[i]) >= 0 && pc[i + p[i]] == pc[i - p[i]]) {
                p[i]++;
            }
            if (i + p[i] > ir) {
                ir = i + p[i];
                ic = i;
            }
        }
        for (int i = 1; i < p.length - 1; i++) {
            if (lLength < p[i]) {
                lLength = p[i];
                lCenterIndex = i;
            }
        }
        return s.substring((lCenterIndex + 1 - lLength) / 2, (lCenterIndex - 1 + lLength) / 2);
    }

}
